It is often necessary to route messages which are generated from a plurality of different sources through output paths which are fewer in number than the number of possible input messages. In other words, the number of input messages must be concentrated in some manner so that a selected number thereof are available at selected routing paths at any one time. If the number of input messages is greater than the number of outputs available for them, certain messages will simply not be able to be handled by the system. The messages which then are not available may be buffered (i.e., held in storage) in some manner so that they can be readily accessed so as to be available at a later time, or they may be re-routed in some other manner through paths in other systems, or they may be fed back to their source with a command that they be re-sent at a later time.
Whatever technique may be used to handle messages that are not transmitted, it is necessary to utilize a suitable technique for concentrating the larger number of messages down to the fewer number of outputs in a manner which is effective in performance and which can be achieved at reasonable cost.
The general problem of handling multiple inputs where fewer outputs are available is discussed in the publication "Graph-Theoretic Properties In Computational Complexity", L. G. Valiant, JCSS, Vol. 13 No. 3, Dec. 1976, pp. 278-285. Such publication generally describes the problem in a graphical sense and broadly discusses what is required but does not disclose any specific implementation technique for resolving the problem in any particular manner.
The publication "Ultracomputers", J. T. Schwartz, ACM Transactions on Programming Languages and Systems, Vol. 2 No. 4, Oct. 1980, pp. 484-521, discusses a similar problem for compacting data information for parallel computations. The technique suggested by Schwartz for routing fewer than the total number of multiple messages which are supplied utilizes relatively complex control circuitry for implementing an algorithm which controls switching in a manner so as to produce the desired concentration of messages. Such algorithm is complex and would be relatively expensive to implement, the size of the system required for such implementation also being larger than is desirable for many applications. Moreover, the overall speed of operation thereof may not be acceptable in many applications.
It is desirable, therefore, to provide a way of concentrating multiple messages to a lesser number thereof in a manner which is both reasonably effective in cost and in speed of performance as well as in the physical size of the system required therefor. Such a technique would be extremely useful when dealing with parallel operating computers so as to handle the outputs of a relatively large number of such computers for routing such outputs in an appropriate concentrating manner. If the speed of operation of the message concentration system is comparable to that of the speed of operation of the computers which are being so serviced, such a concentrator switch technique would be of great assistance in dealing with such parallel processor network operations.